package com.leetcode.string;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
 *
 * 示例 1:
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * 示例 2:
 * 输入: s = "rat", t = "car"
 * 输出: false
 *  
 * 提示:
 * 1 <= s.length, t.length <= 5 * 104
 * s 和 t 仅包含小写字母
 *  
 * 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class IsAnagramTest {
    public static void main(String[] args) {
        String s = "anagram";
        String t = "nagaram";

        /*String s = "rat";
        String t = "car";*/

        //boolean anagram = isAnagram(s, t);
        boolean anagram2 = isAnagram2(s, t);
        System.out.println(anagram2);
    }
    //判断 t 是否是 s 的字母异位词。

    /**
     * 方法一:使用排序的方法,
     * 1 首先判断两个字符串的长度,若长度不同,证明必然不是字母异位词
     * 2 导入Arrays包,通过sort方法排序,故需要经字符串转为字符数组
     * 3  调用Arrays的equals方法,查看两个字符数组是否相等,返回结果
     * @param s
     * @param t
     * @return boolean
     */
    public static boolean isAnagram(String s, String t) {
        //判断字符串长度
        if(s.length() != t.length()){
            return  false;
        }
        //将字符串转为字符数组
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        //调用sort方法,对字符数组进行排序
        Arrays.sort(str1);
        Arrays.sort(str2);
        //调用equals方法,返回是否为字母异位词
        boolean equals = Arrays.equals(str1, str2);
        return equals;
    }

    /**
     * 方法二 使用数组标记
     * 1 首先判断长度,不相等直接返回false
     * 2 创建一个长度为26的int数组,用于记录s字符串中,会出现的字符
     * 3 遍历s字符串,使用s.charAt(i)-'a'获得当前字符为26个英文字符在数组的位置,并且++
     * 4 遍历t字符串,同样使用t.charAt(i)-'a',获得当前字符在数组位置,--;
     * 5 一旦数值当前位置,保存的数值小于0,代表两者不是字母异位词
     * @param s
     * @param t
     * @return
     */
    public static boolean isAnagram2(String s, String t) {
        //判断字符串长度
        if(s.length() != t.length()){
            return  false;
        }
        //创建长度为26的int数组
        int[] ints = new int[26];
        //遍历字符串s
        for (int i = 0; i < s.length(); i++) {
            //找到当前字符位置++
            ints[s.charAt(i) - 'a']++;
        }
        //遍历字符串t
        for (int i = 0; i < t.length(); i++) {
            //找到当前字符在数组的位置--;与s字符串做对比
            ints[t.charAt(i) - 'a']--;
            //若过数组当前位置小于0,证明两者不是字母异位词
            if (ints[t.charAt(i) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
}
